0/1 Knapsack Approaches

Algorithm analysis & benchmarking — algoscope

Notes

Comparison of brute force, recursion, memoization, tabulation, and 1D DP.

Beginner Summary

knapsack_bruteforce

When the input size n doubles, the runtime grows by approximately 4.63×, which suggests performance closest to O(n log n).

knapsack_recursive

When the input size n doubles, the runtime grows by approximately 2.97×, which suggests performance closest to O(n log n).

knapsack_memo

When the input size n doubles, the runtime grows by approximately 1.60×, which suggests performance closer to O(n).

knapsack_tab

When the input size n doubles, the runtime grows by approximately 1.50×, which suggests performance closer to O(n).

knapsack_1d

When the input size n doubles, the runtime grows by approximately 1.49×, which suggests performance closer to O(log n).

Interview Summary

knapsack_bruteforce

knapsack_bruteforce has estimated time complexity O(n^2) and space complexity O(1). These results are heuristic; empirical benchmarks confirm scaling.

knapsack_recursive

knapsack_recursive has estimated time complexity O(2^n) and space complexity O(n). These results are heuristic; empirical benchmarks confirm scaling.

knapsack_memo

knapsack_memo has estimated time complexity O(2^n) and space complexity O(n). These results are heuristic; empirical benchmarks confirm scaling.

knapsack_tab

knapsack_tab has estimated time complexity O(n·W) and space complexity O(n·W). These results are heuristic; empirical benchmarks confirm scaling.

knapsack_1d

knapsack_1d has estimated time complexity O(n·W) and space complexity O(n·W). These results are heuristic; empirical benchmarks confirm scaling.

Quick Stats

6 input sizes • 6 measured points

Manual Big-O Analysis

knapsack_bruteforce

Time: O(n^2) • Space: O(1)

Why: Nested loops detected → quadratic time. These are heuristics; empirical results below provide a practical check.

knapsack_recursive

Time: O(2^n) • Space: O(n)

Why: Multiple recursive calls per invocation detected → exponential recursion tree. These are heuristics; empirical results below provide a practical check.

knapsack_memo

Time: O(2^n) • Space: O(n)

Why: Multiple recursive calls per invocation detected → exponential recursion tree. These are heuristics; empirical results below provide a practical check.

knapsack_tab

Time: O(n·W) • Space: O(n·W)

Why: DP array usage detected → table-filling DP complexity. These are heuristics; empirical results below provide a practical check.

knapsack_1d

Time: O(n·W) • Space: O(n·W)

Why: DP array usage detected → table-filling DP complexity. These are heuristics; empirical results below provide a practical check.

Performance Overview

Combined runtime, memory, and rank summary

Complexity Analysis

knapsack_bruteforce

Heuristic Guess

Dynamic Guess

knapsack_recursive

Heuristic Guess

Dynamic Guess

knapsack_memo

Heuristic Guess

Dynamic Guess

knapsack_tab

Heuristic Guess

Dynamic Guess

knapsack_1d

Heuristic Guess

Dynamic Guess

Runtime Chart

Memory Chart

Comparison Summary

nBestWorstRanks
5 knapsack_1d knapsack_bruteforce knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00
7 knapsack_1d knapsack_bruteforce knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00
9 knapsack_1d knapsack_bruteforce knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00
11 knapsack_1d knapsack_bruteforce knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00
13 knapsack_1d knapsack_bruteforce knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00
15 knapsack_1d knapsack_bruteforce knapsack_bruteforce: 5.00 knapsack_recursive: 3.67 knapsack_memo: 3.17 knapsack_tab: 2.17 knapsack_1d: 1.00

Methods & Notes

  • Runtime measured with time.perf_counter(); each (function, n) pair ran 3 times after 2 warmup iterations. GC was enabled and collected before runs.
  • Memory peak measured with tracemalloc backend (tracemalloc by default).
  • Confidence Intervals: T at 95% confidence. T-intervals use standard t critical values; bootstrap uses 2,000 resamples with a fixed seed.
  • Reference curves (O(1), O(log n), O(n), O(n log n), plus any custom) were normalized at the largest n to match the average observed runtime scale.